﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace gemGenerator
{
    public static class Op
    {
       
        internal static VectorL Cross(VectorL v1, VectorL v2)
        {
            
            var r = new VectorL(v1.Y * v2.Z - v1.Z * v2.Y,
                              v1.Z * v2.X - v1.X * v2.Z,
                              v1.X * v2.Y - v1.Y * v2.X);
            return r;
        }
        public static VectorD Cross(VectorD v1, VectorD v2)
        {
            VectorD ret = new VectorD(v1.Y * v2.Z - v1.Z * v2.Y,
                              v1.Z * v2.X - v1.X * v2.Z,
                              v1.X * v2.Y - v1.Y * v2.X);
            return ret;
        }
        internal static VectorL Normal(VectorL v0, VectorL v1, VectorL v2)
        {
            return Cross(v1 - v0, v2 - v0);
        }
        public static VectorD Normal(VectorD v0, VectorD v1, VectorD v2)
        {
            return Normalize(Cross(v1 - v0, v2 - v0));
        }
        public static VectorD Normal(IList<VectorD> vertices, int t1, int t2, int t3)
        {
            return Normal(vertices[t1], vertices[t2], vertices[t3]);
        }
        public static VectorD Normal(IList<VectorD> vertices, Triangle t)
        {
            return Normal(vertices, t.V1, t.V2, t.V3);
        }


        internal static long Dot(VectorL v1, VectorL v2)
        {
            return v1.X * v2.X + v1.Y * v2.Y + v1.Z * v2.Z;
        }
        public static double Dot(VectorD v1, VectorD v2)
        {
            return v1.X * v2.X + v1.Y * v2.Y + v1.Z * v2.Z;
        }
        internal static VectorL ToInteger(VectorD v)
        {
            const int scl = 10000;
            var r = new VectorL(
                (long)(scl * v.X),
                (long)(scl * v.Y),
                (long)(scl * v.Z));
            r.VisibleTris = new Dictionary<LinkedListNode<Triangle>,char>();
            return r;
        }
        public static VectorD Normalize(VectorD v)
        {
            return (1 / Math.Sqrt( Dot(v, v))) * v;
        }
    }
    class VectorL
    { //for convex hull computation
        public long X = 0, Y = 0, Z = 0;
        public VectorL(long x, long y, long z)
        {
            X = x; Y = y; Z = z;
        }
        public static VectorL operator -(VectorL v1, VectorL v2)
        {
            return new VectorL(v1.X - v2.X, v1.Y - v2.Y, v1.Z - v2.Z);
        }
        public static VectorL operator +(VectorL v1, VectorL v2)
        {
            return new VectorL(v1.X + v2.X, v1.Y + v2.Y, v1.Z + v2.Z);
        }
        public static VectorL operator *(long t, VectorL v2)
        {
            return new VectorL(t * v2.X, t * v2.Y, t * v2.Z);
        }
        public Dictionary<LinkedListNode<Triangle>, char> VisibleTris = null; //for conflict graph
    }
    public class VectorD
    {  //for general use
        public double X = 0, Y = 0, Z = 0;
        public VectorD(double x, double y, double z)
        {
            X = x; Y = y; Z = z;
        }
        public static VectorD operator -(VectorD v1, VectorD v2)
        {
            return new VectorD(v1.X - v2.X, v1.Y - v2.Y, v1.Z - v2.Z);
        }
        public static VectorD operator +(VectorD v1, VectorD v2)
        {
            return new VectorD(v1.X + v2.X, v1.Y + v2.Y, v1.Z + v2.Z);
        }
        public static VectorD operator *(double t, VectorD v2)
        {
            return new VectorD(t * v2.X, t * v2.Y, t * v2.Z);
        }

    }
    public class Triangle
    { 
        public int V1, V2, V3; //my vertices 
        public int ProcessedInIteration = 0;
        public int boundarycount = 0;
        public Triangle(int v1, int v2, int v3)
        {   
            V1 = v1; V2 = v2; V3 = v3;
        }
        public int Third(int a, int b)
        {//return that which is neither a or b
            return (V1 != a ?
                       (V1 != b ? V1 //it's v1
                            :(V2 != a ? V2 //v1==b
                                : V3))   //v1 == b, v2 == a
                      
                      :
 
                      (V2 != b ? V2 //v1==a
                        : V3)) //v1==a, v2==b
            ; 
                                    
                   
        }

        public Dictionary<int, char> VerticesAbove = new Dictionary<int, char>();//for conflict graph
    }
    public struct EdgeKey
    {
        public int V1, V2; //my vertices, sorted
        public EdgeKey(int v1, int v2)
        {
            if(v1<v2)
            {
                V1 = v1; V2 = v2;
            }
            else
            {   
                V1 = v2; V2 = v1;
            }
        }
    }
    public class EdgeWings
    {
        public LinkedListNode<Triangle> T1 = null, T2=null; //adjacent triangles
        public EdgeWings(LinkedListNode<Triangle> t1, LinkedListNode<Triangle> t2)
        {
            T1 = t1; T2 = t2;
        }
        public void SwapSides()
        {
            LinkedListNode<Triangle> t = T1;
            T1 = T2;
            T2 = t;
        }
    }

    public static class ConvexHullBuilder
    {
       //conflict graph operations
        static void Connect(IList<VectorL> vertices, int vertex, LinkedListNode<Triangle> triangle)
        {
            vertices[vertex].VisibleTris.Add(triangle,'0');
            triangle.Value.VerticesAbove.Add(vertex,'0');
        }
        static void AdoptVisibleVertices(IList<VectorL> vertices, EdgeWings edge, LinkedListNode<Triangle> triangle)
        {  //conflick graph update for new triangle
            var visibles = triangle.Value.VerticesAbove;
            foreach (var v in edge.T1.Value.VerticesAbove)
            {
                if (!visibles.ContainsKey(v.Key) && IsFaceBad(vertices, triangle.Value, v.Key))
                {
                    Connect(vertices, v.Key, triangle);
                }
            }
            foreach (var v in edge.T2.Value.VerticesAbove)
            {
                if (!visibles.ContainsKey(v.Key) && IsFaceBad(vertices, triangle.Value, v.Key))
                    Connect(vertices, v.Key, triangle);
            }
        }
        static void InititializeConflictGraph(IList<VectorL> vertices, LinkedList<Triangle> thd)
        {
            LinkedListNode<Triangle> tri = thd.First;
            while (tri != null)
            {
                for (int i = 3; i < vertices.Count; ++i)
                {
                    if (vertices[i].VisibleTris == null) continue;
                    if (IsFaceBad(vertices, tri.Value, i))
                        Connect(vertices, i, tri);
                }
                tri = tri.Next;
            }
        }


        static Triangle TriangleOverVertex(IList<VectorL> vertices, int t1, int t2, int t3, int insider)
        {
            return TriangleOverVertex(vertices, t1, t2, t3, vertices[insider]);
        }
        static VectorL Normal(IList<VectorL> vertices, int t1, int t2, int t3)
        {
            return Op.Normal(vertices[t1], vertices[t2], vertices[t3]);
        }
        static VectorL Normal(IList<VectorL> vertices, Triangle t)
        {
            return Normal(vertices, t.V1, t.V2, t.V3);
        }
        static long Dot(IList<VectorL> vertices, int t1, int t2)
        {
            return Op.Dot(vertices[t1], vertices[t2]);
        }
        static long Dot(VectorL t1, VectorL t2)
        {
            return Op.Dot(t1, t2);
        }

        static Triangle TriangleOverVertex(IList<VectorL> vertices, int t1, int t2, int t3, VectorL insider)
        {//creates triangle so that normal is facing away from <insider>
            Triangle candidate1 = new Triangle(t1,t2,t3);
            if (IsFaceBad(vertices, candidate1, insider))
                return new Triangle(t1, t3, t2);
            else
                return candidate1;
        }
        static void AddEdge(IDictionary<EdgeKey, EdgeWings> edges, int v1, int v2, LinkedListNode<Triangle> t1, LinkedListNode<Triangle> t2)
        {
           edges.Add(new KeyValuePair<EdgeKey, EdgeWings>(new EdgeKey(v1, v2), new EdgeWings(t1, t2))); 
        }
        static T GetVal<T>(IDictionary<EdgeKey, T> edges, int v1, int v2)
        {
            EdgeKey k = new EdgeKey(v1,v2);
            if(!edges.ContainsKey(k)) return default(T);
            return edges[k];
        }

        static LinkedList<Triangle> FirstTetrahedron(IList<VectorL> vertices, IDictionary<EdgeKey, EdgeWings> edges)
        {
            if(vertices.Count<4) return null;
            var normal = Normal(vertices, new Triangle(0,1,2));
            
            //find best fourth vertex
            long refd = Dot(vertices[0], normal);
            long bestd = 0;
            int b = 0;
            for (int i = 3; i < vertices.Count; ++i)
            {
                long d = Math.Abs(refd-Dot(vertices[i], normal));
                if (d> bestd)
                {
                    bestd = d;
                    b = i;
                }
            }
            if(b<3) return null;
            
            LinkedList<Triangle> thd = new LinkedList<Triangle>();
            LinkedListNode<Triangle> t012 = thd.AddFirst(TriangleOverVertex(vertices, 0, 1, 2, b)),
                                     t013 = thd.AddFirst(TriangleOverVertex(vertices, 0, 1, b, 2)),
                                     t023 = thd.AddFirst(TriangleOverVertex(vertices, 0, 2, b, 1)),
                                     t123 = thd.AddFirst(TriangleOverVertex(vertices, 1, 2, b, 0));

            AddEdge(edges, 0, 1, t012, t013);
            AddEdge(edges, 0, 2, t012, t023);
            AddEdge(edges, 0, b, t013, t023);
            AddEdge(edges, 1, 2, t012, t123);
            AddEdge(edges, 1, b, t013, t123);
            AddEdge(edges, 2, b, t023, t123);
            
            vertices[0].VisibleTris = null;
            vertices[1].VisibleTris = null;
            vertices[2].VisibleTris = null;
            vertices[b].VisibleTris = null;
            return thd;
        }
        static bool IsFaceBad(IList<VectorL> vertices, Triangle face, int vertex, int iteration = 0)
        { //face is bad when a vertex is in above it
            return IsFaceBad(vertices, face, vertices[vertex], iteration);
        }
        static bool IsFaceBad(IList<VectorL> vertices, Triangle face, VectorL vertex, int iteration = 0)
        { //face is bad when a vertex is above it
            VectorL normal = Normal(vertices, face);
            long diff = Op.Dot(normal, vertex - vertices[face.V1]);
            return diff >0;
        }
        static void UnbindNodes(IList<VectorL> vertices, IDictionary<LinkedListNode<Triangle>, char> bads)
        { //delete data of conflict graph from removed faces
            foreach (var tr in bads)
            {
                foreach (var v in tr.Key.Value.VerticesAbove)
                {
                    if (vertices[v.Key].VisibleTris != null)
                        vertices[v.Key].VisibleTris.Remove(tr.Key);
                }
                tr.Key.List.Remove(tr.Key);
            }
        }
        static IDictionary<LinkedListNode<Triangle>,char> FindOffenders(IList<VectorL> vertices, LinkedList<Triangle> faces, int vertex)
        { //find bad triangles for a vertex = consult conflict graph
            var bads = vertices[vertex].VisibleTris;
            vertices[vertex].VisibleTris = null;
            return bads;
        }

        static void ConnectVertexToHull(IList<VectorL> vertices, LinkedList<Triangle> faces, IDictionary<EdgeKey, EdgeWings> edges, IDictionary<EdgeKey, EdgeWings> holeEdge, int vertex, VectorL inside)
        { //connect edges of the hole with the new vertex
            IDictionary<int, LinkedListNode<Triangle>> edgeVertices = new Dictionary<int, LinkedListNode<Triangle>>();
            foreach (var e in holeEdge)
            {
                LinkedListNode<Triangle> ntr = faces.AddFirst(TriangleOverVertex(vertices, e.Key.V1, e.Key.V2, vertex, inside));
                AdoptVisibleVertices(vertices, e.Value, ntr);
                
                if (edgeVertices.ContainsKey(e.Key.V1))
                    AddEdge(edges, e.Key.V1, vertex, edgeVertices[e.Key.V1], ntr);
                else
                    edgeVertices.Add(e.Key.V1, ntr);

                if (edgeVertices.ContainsKey(e.Key.V2))
                    AddEdge(edges, e.Key.V2, vertex, edgeVertices[e.Key.V2], ntr);
                else
                    edgeVertices.Add(e.Key.V2, ntr);

                edges.Add(e.Key, new EdgeWings(e.Value.T1, ntr));
            }
            edgeVertices.Clear();
        }

        static IDictionary<EdgeKey, EdgeWings> CreateHoleEdge(IList<VectorL> vertices, LinkedList<Triangle> faces, IDictionary<EdgeKey, EdgeWings> edges, IDictionary<LinkedListNode<Triangle>,char> badFaces, int nvertex /*for dege cases*/)
        { //find edges that bound bad triangles area
            IDictionary<EdgeKey, EdgeWings> holeEdge = new Dictionary<EdgeKey, EdgeWings>();
            foreach (var f in badFaces)
            {
                XorEdges(f.Key.Value, edges, holeEdge); //T1 is the outside
            }
            return holeEdge;
        }
        static void XorEdges(Triangle f, IDictionary<EdgeKey, EdgeWings> edges, IDictionary<EdgeKey, EdgeWings> bound)
        {
            int a = f.V1, b = f.V2, c = f.V3;
            XorEdge(f, a, b, edges, bound);
            XorEdge(f, a, c, edges, bound);
            XorEdge(f, c, b, edges, bound);
        }
        static void XorEdge(Triangle f, int a, int b, IDictionary<EdgeKey, EdgeWings> edges, IDictionary<EdgeKey, EdgeWings> bound)
        {
            EdgeKey k = new EdgeKey(a,b);
            if (bound.ContainsKey(k))
                bound.Remove(k);
            else
            {
                EdgeWings adj = edges[k];
                edges.Remove(k);
                if (adj.T1.Value == f) adj.SwapSides(); //T1 = outside hole
                bound.Add(k, adj );
            }
        }
        static IList<VectorL> ConvertVectors(IList<VectorD> verticesD)
        { 
            var vertices = new List<VectorL>(verticesD.Count);
            
            foreach(VectorD v in verticesD)
            {
                vertices.Add( Op.ToInteger(v) );
            }
            return vertices;
        }
        static VectorL TetrahedronCenter(IList<VectorL> vertices, LinkedList<Triangle> thd)
        { //to obtain a vertex inside all partial convex hulls
            //needed for determining faces' orientation
            if(thd.Count<4) return null;
            List<VectorL> myv = new List<VectorL>(12);
            foreach(Triangle t in thd)
            {
                myv.Add(vertices[t.V1]);
                myv.Add(vertices[t.V2]);
                myv.Add(vertices[t.V3]);
            }
            VectorL ret = new VectorL(0, 0, 0);
            foreach (var v in myv)
            {
                ret.X += v.X;
                ret.Y += v.Y;
                ret.Z += v.Z;
            }
            long div = myv.Count;
            ret.X /= div;
            ret.Y /= div;
            ret.Z /= div;
            return ret;
        }
        /// <summary>
        /// Compute convex hull of a set of vertices
        /// </summary>
        /// <param name="verticesD">list of input vertices</param>
        /// <returns>list of triangles forming the hull</returns>
        public static LinkedList<Triangle> GetHull(IList<VectorD> verticesD)
        {
            IDictionary<EdgeKey, EdgeWings> edges;
            return GetHull(verticesD, out edges);
        }
        public static LinkedList<Triangle> GetHull(IList<VectorD> verticesD, out IDictionary<EdgeKey, EdgeWings> edges)
        {
            //IDictionary<EdgeKey, EdgeWings> 
            edges = new Dictionary<EdgeKey, EdgeWings>();
            
            //use integer values for absolute precision
            var vertices = ConvertVectors(verticesD);
            //start with an always-convex tetrahedron
            LinkedList<Triangle> hull = FirstTetrahedron(vertices, edges);
            if (hull==null) return null; //either too little vertices or all are in one plane
            VectorL inside = TetrahedronCenter(vertices, hull);
            InititializeConflictGraph(vertices, hull);
            //then add vertices one by one 
            for (int i = 3; i < vertices.Count; ++i)
            {
                var bads = FindOffenders(vertices, hull, i);
                if (bads==null || bads.Count < 1)
                {//all is good
                    continue;
                }
                
                //hull needs to be updated
                var hole = CreateHoleEdge(vertices, hull, edges, bads, i);
                ConnectVertexToHull(vertices, hull, edges, hole, i, inside);
                UnbindNodes(vertices, bads);
            }
            return hull;
        }
        static bool IsConvex(IList<VectorL> vertices, LinkedList<Triangle> faces)
        {//test function
            foreach (Triangle t in faces)
                foreach (var v in vertices)
                    if (v != vertices[t.V1] && v != vertices[t.V2] && v != vertices[t.V3]
                        &&
                        IsFaceBad(vertices, t, v))
                        return false;
            return true;
        }
    }
}
